package com.gwcloud.leetcode.hot100;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/** 
* @ClassName   : Leetcode0347 
* @author      : ganwei 
* @date        : 2020年5月23日 
* @Description : TODO 
*/
public class Leetcode0347 {
    /**
     * -解题思路，最小堆解法
     */
	public int[] topKFrequent(int[] nums, int k) {
		HashMap<Integer, Integer> map = new HashMap<>();
		for(int num : nums) {
			if(map.containsKey(num)) {
				map.put(num, map.get(num) + 1);
			}else {
				map.put(num, 1);
			}
		}
		
        // 遍历map，用最小堆保存频率最大的k个元素
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        
        for(Integer key : map.keySet()) {
        	if(pq.size() < k) {
        		pq.add(key);
        	}else if(map.get(key) > map.get(pq.peek())) {
        		pq.remove();
        		pq.add(key);
        	}
        }
		
        int[] maxk = new int[k];
        int index = 0;
        while(!pq.isEmpty()) {
        	maxk[index] = pq.remove();
        	index++;
        }
		
		return maxk;
    }
    
	/**
	 * -主函数
	 */
	public static void main(String[] args) {
		
	}
}
